package com.ljx.QueueStack;

/**
 * @author 李加喜
 * @Package com.ljx.QueueStack
 * @date 2021-12-02 23:58
 */
// 奇数情况不理解
public class MinKuoHaoNum {
    public static void main(String[] args) {
        MinKuoHaoNum minKuoHaoNum = new MinKuoHaoNum();
        int i = minKuoHaoNum.minInsertions("(()))(()))()())))");
        System.out.println(i);
    }
    public int minInsertions(String s) {
        int res=0,need=0;
        char[] cs = s.toCharArray();
        for (char c:cs){
            if (c=='('){
                //需要的)数量
                need+=2;
                //如果)奇数的时候  因为(对应两个) 所以一定是偶数
                if (need%2==1){
                    //右边括号+1
                    need--;
                    res++;
                }
            }
            if (c==')'){
                need--;
                if (need==-1){
                    //多了一个)  所以这个时候需要添加一个做  并且还需要一个)  所以need==1
                    need=1;
                    res++;
                }
            }
        }
        return res+need;
    }
}
